package cn.corffen.test.algorithm.leetcode.easy.math;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class EasyMath {

    /**
     * 写一个程序，输出从 1 到 n 数字的字符串表示。
     * <p>
     * 1. 如果 n 是3的倍数，输出“Fizz”；
     * <p>
     * 2. 如果 n 是5的倍数，输出“Buzz”；
     * <p>
     * 3.如果 n 同时是3和5的倍数，输出 “FizzBuzz”。
     * <p>
     * 示例：
     * <p>
     * n = 15,
     * <p>
     * 返回:
     * [
     * "1",
     * "2",
     * "Fizz",
     * "4",
     * "Buzz",
     * "Fizz",
     * "7",
     * "8",
     * "Fizz",
     * "Buzz",
     * "11",
     * "Fizz",
     * "13",
     * "14",
     * "FizzBuzz"
     * ]
     *
     * @param n
     * @return
     */
    public List<String> fizzBuzz(int n) {
        List<String> list = new ArrayList<>();
        for (int i = 1; i <= n; i++) {
            if (i % 3 == 0 && i % 5 == 0) {
                list.add("FizzBuzz");
            } else if (i % 3 == 0) {
                list.add("Fizz");
            } else if (i % 5 == 0) {
                list.add("Buzz");
            } else {
                list.add(String.valueOf(i));
            }
        }
        return list;
    }

    /**
     * 统计所有小于非负整数 n 的质数的数量。
     * <p>
     * 示例:
     * <p>
     * 输入: 10
     * 输出: 4
     * 解释: 小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。
     *
     * @param n
     * @return
     */
    public int countPrimes(int n) {
        if (n < 2) {
            return 0;
        }
        int count = 1;
        for (int i = 3; i <= n; i++) {
            boolean sign = true;
            if (i % 2 == 0) {
                continue;
            }
            for (int j = 3; j * j <= i; j += 2) {
                if (i % j == 0) {
                    sign = false;
                    break;
                }
            }
            if (sign) {
                count++;
            }
        }
        return count;
    }

    public int countPrimes2(int n) {
        int result = 0;
        boolean[] b = new boolean[n];
        if (n > 2) {
            result++;
        }
        //从奇数开始,每次加2,就遍历的是他的奇数
        //因为>2的偶数不可能是质数.
        for (int i = 3; i < n; i += 2) {
            if (!b[i]) {
                for (int j = 3; i * j < n; j += 2) {
                    b[i * j] = true;//b[i]如果是质数,那么他的奇数倍都不是质数.
                }
                result++;
            }
        }
        return result;
    }

    public boolean isPowerOfThree(int n) {
        if (n < 1) {
            return false;
        }
        while (n % 3 == 0) {
            n /= 3;
        }
        return n == 1;
    }

    /**
     * 如果n是10进制的数,那么10,100,1000 就是10的幂次方
     * 如果n是2进制的数,那么10,100,1000就是2的幂次方
     * 同样的如果n是3进制的数,那么10,100,1000就是3的幂次方
     * <p>
     * 知识点,如何将一个正整数转换成3进制的数
     * 对于字符串的匹配.以1开头,后面跟上0个或者多个0
     *
     * @param n
     * @return
     */
    public boolean isPowerOfThree2(int n) {
        return Integer.toString(n, 3).matches("^10*$");
    }

    /**
     * sum为最后一位的值
     * 向前遍历.如果前一位的数比后面一位的小,sum就减去这个前一位的数
     * 如果前一位的数比后面的大或者等于,sum就加上这个前一位的数.
     *
     * @param s
     * @return
     */
    public int romanToInt(String s) {
        if (s == null || s.length() < 1) {
            return 0;
        }
        Map<Character, Integer> map = new HashMap<>();
        map.put('I', 1);
        map.put('V', 5);
        map.put('X', 10);
        map.put('L', 50);
        map.put('C', 100);
        map.put('D', 500);
        map.put('M', 1000);
        int len = s.length();
        int sum = map.get(s.charAt(len - 1));
        for (int i = len - 2; i >= 0; i--) {
            if (map.get(s.charAt(i)) < map.get(s.charAt(i + 1))) {
                sum -= map.get(s.charAt(i));
            } else {
                sum += map.get(s.charAt(i));
            }
        }
        return sum;
    }
}
